//Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k
//]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. 
//
// Notice that the solution set must not contain duplicate triplets. 
//
// 
// Example 1: 
// Input: nums = [-1,0,1,2,-1,-4]
//Output: [[-1,-1,2],[-1,0,1]]
// Example 2: 
// Input: nums = []
//Output: []
// Example 3: 
// Input: nums = [0]
//Output: []
// 
// 
// Constraints: 
//
// 
// 0 <= nums.length <= 3000 
// -105 <= nums[i] <= 105 
// 
// Related Topics 数组 双指针 
// 👍 3335 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：3Sum
class P15ThreeSum {
    public static void main(String[] args) {
        Solution solution = new P15ThreeSum().new Solution();
        // TO TEST
//        System.out.println(solution.threeSum(new int[]{-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6}));
        System.out.println(solution.threeSum(new int[]{0, 0, 0}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            if (nums == null || nums.length == 0) {
                return list;
            }
            if (nums.length == 1) {
                return list;
            }
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 2; i++) {
                if (nums[i] > 0) {
                    break;
                }
                if (i > 0 && nums[i - 1] == nums[i]) {
                    continue;
                }
                int target = -nums[i];
                Map<Integer, Boolean> map = new HashMap<>();
                for (int j = i + 1; j < nums.length; j++) {
                    int num1 = nums[j];
                    int num2 = target - num1;
                    if (map.containsKey(num1) && map.get(num1)) {
                        continue;
                    }
                    if (map.containsKey(num2)) {
                        ArrayList<Integer> integers = new ArrayList<>(Arrays.asList(nums[i], num2, num1));
                        list.add(integers);
                        map.put(num1, true);
                        continue;
                    }
                    map.put(num1, false);
                }
            }

            return list;

        }

        public List<List<Integer>> threeSumRight(int[] nums) {// 总时间复杂度：O(n^2)
            List<List<Integer>> ans = new ArrayList<>();
            if (nums == null || nums.length <= 2) {
                return ans;
            }

            Arrays.sort(nums); // O(nlogn)

            for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
                if (nums[i] > 0) {
                    break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
                }
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue; // 去掉重复情况
                }
                int target = -nums[i];
                int left = i + 1, right = nums.length - 1;
                while (left < right) {
                    if (nums[left] + nums[right] == target) {
                        ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                        // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                        left++;
                        right--; // 首先无论如何先要进行加减操作
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else if (nums[left] + nums[right] < target) {
                        left++;
                    } else {  // nums[left] + nums[right] > target
                        right--;
                    }
                }
            }
            return ans;

        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}